package Sort_work;

import java.util.Arrays;

/**
 * 选择排序
 * 时间复杂度：O（N^2）
 * 空间复杂度：O（1）
 * 稳定性：不稳定
 */
public class Select_Sort {
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    public static void swap(int[] array,int x,int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }
    //////////////////////////////////////////
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right; i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    minIndex = i;
                }
            }
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,left,minIndex);
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] array = {1,3,5,7,9,2,4,6,8};
        selectSort(array);
        System.out.println(Arrays.toString(array));
    }
}
